PC World Komputer 2010 April/PCWorld0410.iso/pluginy Firefox/13316/13316.xpi/content/treeArranger.js

JavaScript | 2009-07-25 | 18.2 KB | 619 lines

/* Copyright (C) 2009 Norman Solomon
 * e-mail: [e-mail]
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the License.
 */

// ******************************************************************************************
// *****                                                                                *****
// *****    This JS file implements Sven Moen's algorithm to arrange a tree for tidy    *****
// *****    drawing. Sven's algorithm ALWAYS lays out the tree horizontally, but it     *****
// *****    has been adjusted here (with functions added) to layout a vertical tree     *****
// *****  --------------------------------------------------------------------------    *****
// *****                                                                                *****
// *****   FIRST THE CLASSES - Passed properties MUST be set when a class is created    *****
// *****    Java variable type declarations are shown in a comment above each class     *****
// *****                                                                                *****
// ******************************************************************************************

// ---------------------------------------------------------------
// TreeNode objects are stored in the global gTreeNodes[] Array
// (TreeNode p, TreeNode c, TreeNode s, int w, int h)
// ---------------------------------------------------------------
var TreeNode = function (p, c, s, w, h)
{
    // ----------------------------------------------------------
    // Props needed for ANY implementation of Sven's algorithm
    // ----------------------------------------------------------
    this.parent = p;
    this.child = c;
    this.sibling = s;

    // Properties that determine node size and overall tree size
    this.width = w;
    this.height = h;
    this.border = 0;

    // Properties calculated in Sven's tArrLayout() method
    this.pos = new Point(0, 0);
    this.offset = new Point(0, 0);
    this.contour = new Polygon();

    // -------------------------------------------------------
    // Properties specific to this FF extension application
    // -------------------------------------------------------
    this.histNode = null;        // Ref to this TreeNodes's associated HistoryNode
    this.isOpenPage = false;    // Set = true if underlying web-page is open in FF

    this.inOpenTab = null;        // Set = true if Tab root TreeNode is open in FF
    this.tabTreeSize = 0;        // Number of TreeNode's in a Tab sub-tree

    this.childCopy = null;        // Used to expand/contract sub-trees
    this.hiddenTreeSize = 0;    // Size of hidden sub-tree below node
    this.hidden = false;        // Set = true if this TreeNode is in hidden sub-tree

    // Props used to restore tree's overall state to its initial state
    this.parentBak = null;
    this.childBak = null;
    this.siblingBak = null;

    // Props for detection of mouse-click on TreeView node
    this.hidBtnWid = 0;
    this.btnPanelWid = 0;
    this.btnPanelX = 0;

    // Props for GridView image drawing and mouse-click detection
    this.gridViewImgX = 0;
    this.gridViewImgY = 0;
    this.gridViewImgWid = 0;
    this.gridViewTabNum = 0;

    // Description strings for text displayed inside this TreeNode
    this.histNodeDesc = "";        // Used to check whether descLine's are up to date
    this.descLine1 = "";        // Set in function setDescriptionLinesFor()
    this.descLine2 = "";        // Set in function setDescriptionLinesFor()
}

// -----------------------------------------------------------------------
// Polylines are used to build the sub-tree contours around each TreeNode
// (int dx, int dy, PolyLine link)
// -----------------------------------------------------------------------
var PolyLine = function (dx, dy, link)
{
    this.dx = dx;
    this.dy = dy;
    this.link = link;
}

// -----------------------------------------------------------------------
// Represents a polygon area for use in spacing/positioning calculations
// *** No props are passed to the class instantiator when object created
// -----------------------------------------------------------------------
var Polygon = function ()
{
    // Four Polyline objects
    this.lower_head;
    this.lower_tail;
    this.upper_head;
    this.upper_tail;
}

// -----------------------------------------------------------------------
// JS equivalent of Java Point object (used by several functions below)
// (int x, int y)
// -----------------------------------------------------------------------
var Point = function (x, y)
{
   this.x = x;
   this.y = y;
}

// ******************************************************
// *****                                            *****
// *****       FUNCTIONS WRITTEN BY Sven Moen       *****
// *****   --------------------------------------   *****
// *****    Java variable type declarations are     *****
// *****    shown in a comment above each method    *****
// *****                                            *****
// ******************************************************

// -----------------------------------------------------------
// Lays out the tree node spacing by setting Node offsets
// (TreeNode t)
// -----------------------------------------------------------
function tArrLayout(t)
{
    var c; // TreeNode

    // ------------------------------------
    // Exit if the passed node is null
    if (t === null)
        return;

    // ***********************************
    // *******   RECURSIVE LOOP   ********
    // ***********************************
    c = t.child;
    while (c != null)
    {
        tArrLayout(c);
        c = c.sibling;
    }

    // ------------------------------------
    // Set contour property of this node
    if (t.child !== null)
        // Create the contour around sub-tree below
        tArrAttachParent(t, tArrJoin(t));
    else
        // Create the contour round ONLY this leaf
        tArrLayoutLeaf(t);
}

// -----------------------------------------------------------
// Attaches specified node to its children, setting offsets
// (TreeNode t, int h)
// -----------------------------------------------------------
function tArrAttachParent(t, h)
{
    var x, y1, y2;

    x = t.border + LEVEL_SPACE;
    y2 = (h - t.height) / 2 - t.border;
    y1 = y2 + t.height + (2 * t.border) - h;

    t.child.offset.x = x + t.width;
    t.child.offset.y = y1;

    // Set contour property of the passed node
    t.contour.upper_head = new PolyLine(t.width, 0, new PolyLine(x, y1, t.contour.upper_head));
    t.contour.lower_head = new PolyLine(t.width, 0, new PolyLine(x, y2, t.contour.lower_head));
}

// -----------------------------------------------------------
// Sets passed nodes contour property using Polyline objects
// (TreeNode t)
// -----------------------------------------------------------
function tArrLayoutLeaf(t)
{
    // Draw a contour around leaf node & store it in the nodes contour property
    t.contour.upper_tail = new PolyLine(t.width + (2 * t.border), 0, null);
    t.contour.upper_head = t.contour.upper_tail;
    t.contour.lower_tail = new PolyLine(0, - t.height - (2 * t.border), null);
    t.contour.lower_head = new PolyLine(t.width + (2 * t.border), 0, t.contour.lower_tail);
}

// -----------------------------------------------------------
// Merges t's children & returns height of resulting contour
// (TreeNode t)
// -----------------------------------------------------------
function tArrJoin(t)
{
    // *** NOTE - t is parent and c are it's children
    var c;            // TreeNode
    var d, h, sum;  // integers

    // --------------------------------------------
    // Set parent contour equal to child contour
    c = t.child;
    t.contour = c.contour;

    // --------------------------------------------
    // Initialize values used in loop
    //sum = h = c.height + 2 * c.border;
    h = c.height + (2 * c.border);
    sum = h;

    // --------------------------------------------
    // Loop round all children of parent t
    c = c.sibling;
    while(c != null)
    {
        d = tArrMerge(t.contour, c.contour);
        c.offset.y = d + h;
        c.offset.x = 0;
        h = c.height + (2 * c.border);
        sum += d + h;

        // Get next child
        c = c.sibling;
    }
    // ---------------------------------
    return sum;
}

// -------------------------------------------------------------------
// Merges two polygons and returns total height of resulting polygon
// (Polygon c1, Polygon c2)
// -------------------------------------------------------------------
function tArrMerge(c1, c2)
{
    // integers
    var x = 0;
    var y = 0;
    var total = 0;
    var d;

    // Polylines
    var lower, upper, b;

    // --------------------------------------
    upper = c1.lower_head;
    lower = c2.upper_head;

    while(lower != null && upper != null)
    {
        // compute tArrOffset total
        d = tArrOffset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
        y += d;
        total += d;

        if (x + lower.dx <= upper.dx)
        {
            y += lower.dy;
            x += lower.dx;
            lower = lower.link;
        }
        else
        {
            y -= upper.dy;
            x -= upper.dx;
            upper = upper.link;
        }
    }

    // -------------------------------------------
    // store result in c1 (calls tArrBridge function)
    if (lower !== null)
    {
        b = tArrBridge(c1.upper_tail, 0, 0, lower, x, y);
        c1.upper_tail = (b.link != null) ? c2.upper_tail : b;
        c1.lower_tail = c2.lower_tail;
    }
    else // (upper)
    {
        b = tArrBridge(c2.lower_tail, x, y, upper, 0, 0);

        if (b.link === null)
            c1.lower_tail = b;
    }

    c1.lower_head = c2.lower_head;

    // -----------------------------------
    // Return the total
    return total;
}

// ------------------------------------------------------------------
// Returns a value used to set contour - Only called from tArrMerge()
// (PolyLine line1, int x1, int y1, PolyLine line2, int x2, int y2)
// ------------------------------------------------------------------
function tArrBridge(line1, x1, y1, line2, x2, y2)
{
    var dy, dx, s;  // integers
    var r;            // Polyline

    dx = x2 + line2.dx - x1;

    if (line2.dx === 0)
    {
        dy = line2.dy;
    }
    else
    {
        s = dx * line2.dy;
        dy = s / line2.dx;
    }

    r = new PolyLine(dx, dy, line2.link);
    line1.link = new PolyLine(0, y2 + line2.dy - dy - y1, r);

    return r;
}

// ---------------------------------------------------------
// Calculates the tArrOffset for specified points
// (int p1, int p2, int a1, int a2, int b1, int b2)
// ---------------------------------------------------------
function tArrOffset(p1, p2, a1, a2, b1, b2)
{
    var d, s, t;  // integers

    if (b1 <= p1 || p1 + a1 <= 0)
        return 0;

    t = b1 * a2 - a1 * b2;
    // ----------------------
    if (t > 0)
    // ----------------------
    {
        if (p1 < 0)
        {
            s = p1 * a2;
            d = s / a1 - p2;
        }
        else if (p1 > 0)
        {
            s = p1 * b2;
            d = s / b1 - p2;
        }
        else
        {
            d = -p2;
        }
    }
    // ----------------------
    else if (b1 < p1 + a1)
    // ----------------------
    {
        s = (b1 - p1) * a2;
        d = b2 - (p2 + s / a1);
    }
    // ----------------------
    else if (b1 > p1 + a1)
    // ----------------------
    {
        s = (a1 + p1) * b2;
        d = s / b1 - (p2 + a2);
    }
    // ----------------------
    else
    // ----------------------
    {
        d = b2 - (p2 + a2);
    }

    // ======================
    if (d > 0)
        return d;
    else
        return 0;
}

// -----------------------------------------------------------------
// Calculates pos.x and pos.y for all nodes by traversing the tree
// and using the nodes offset.x and offset.y values
// (TreeNode t, int off_x, int off_y)
// -----------------------------------------------------------------
function tArrPlantTree(t, off_x, off_y)
{
    var c, s;    // TreeNodes
    var cur_y;  // integer

    // --------------------------------
    // Set node screen (x,y) position
    t.pos.x = off_x + t.offset.x;
    t.pos.y = off_y + t.offset.y;

    // --------------------------------
    // Set global for whole tree
    if (t.pos.y < gTreeMinY)
        gTreeMinY = t.pos.y;

    // --------------------------------
    // Plant child node
    c = t.child;
    if(c !== null)
    {
        // ***********************************
        // *******   RECURSIVE CALL   ********
        // ***********************************
        tArrPlantTree(c, t.pos.x, t.pos.y);

        // Plant sibling nodes
        s = c.sibling;
        cur_y = t.pos.y + c.offset.y;

        while(s != null)
        {
            // ***********************************
            // *******   RECURSIVE CALL   ********
            // ***********************************
            tArrPlantTree(s, t.pos.x + c.offset.x, cur_y);
            cur_y += s.offset.y;
            s = s.sibling;
        }
    }
}


// ********************************************************************************
// *****                                                                      *****
// *****    PROCEDURES ADDED TO Sven Moen's algorithm TO ALLOW VERTICAL          *****
// *****    TREES TO BE LAID OUT TIDILY - INCLUDING SOME USEFUL UTILITY       *****
// *****    FUNCTIONS FOR ANY IMPLEMENTATION OF THE Sven Moen algorithm          *****
// *****  ------------------------------------------------------------------  *****
// *****   Java type declarations are shown in a comment above each method    *****
// *****                                                                      *****
// ********************************************************************************

// ----------------------------------------------------------------------------
// 1) Adjusts horizontal tree position so it fits snugly in top left corner
// 2) Changes tree to vertical orientation by swapping all TreeNode.(x,y)
// *** NOTE - Sven Moen's algorithm ALWAYS lays out tree horizontally
// (TreeNode root)
// ----------------------------------------------------------------------------
function changeTreeToVerticalLayout(root)
{
    // Initialize global variable
    gTreeMinY = 0;    // integer

    // Private variables
    var node;        // TreeNode
    var tempX;        // integer
    var yAddOn = 0;
    if (root.child !== null)
    {
        node = root.child;
        yAddOn = node.height - BOX_HEIGHT;
    }

    // -----------------------------------------------
    // *** NOTE - tArrPlantTree is a recursive procedure
    tArrPlantTree(root, 0, 0);
    tArrPlantTree(root, 0, Math.abs(gTreeMinY));

    // Change tree to vertical orientation by swapping all TreeNode.(x,y)
    for (var i = 0; i < gTreeNodes.length; i++)
    {
        // Get TreeNode from gTreeNodes[] and swap (x,y)
        node = gTreeNodes[i];
        if (!node.hidden)
        {
            // Swap x and y co-ordinates
            tempX = node.pos.x;
            node.pos.x = node.pos.y;
            node.pos.y = tempX;

            // Adjust for taller Tab roots
            if (node.height > BOX_HEIGHT)
                node.pos.x += Math.round(yAddOn / 2);
            else if (node !== root)
                node.pos.y += yAddOn;
        }
    }
}

// ==========================================================
// Sets left/top border for all TreeNode's drawn on gCanvas
// (int leftBord, int topBord)
// ----------------------------------------------------------
function setLeftAndTopBorderForWholeTree(leftBord, topBord)
{
    var node;   // TreeNode
    for (var i = 0; i < gTreeNodes.length; i++)
    {
        // Get TreeNode from gTreeNodes[]
        node = gTreeNodes[i];
        if (!node.hidden)
        {
            node.pos.x += leftBord;
            node.pos.y += topBord;
        }
    }
}

// ===============================================================
// Sets border for all nodes - which determines overall tree size
// (int bordSize)
// ---------------------------------------------------------------
function setBorderForAllNodes(bordSize)
{
    var node;   // TreeNode
    for (var i = 0; i < gTreeNodes.length; i++)
    {
        // Get TreeNode from gTreeNodes[] and set its border
        node = gTreeNodes[i];
        node.border = bordSize;
    }
}

// ============================================================
// Returns width and height of the whole tree as a Point(x,y)
// ------------------------------------------------------------
function treeDimensions()
{
    // TreeNode and 6 integers
    var node;
    var minX = 0;
    var maxX = 0;
    var minY = 0;
    var maxY = 0;
    var tWid = 0;
    var tHgt = 0;

    // -----------------------------------------
    for (var i = 0; i < gTreeNodes.length; i++)
    {
        // Get TreeNode from gTreeNodes[]
        node = gTreeNodes[i];
        if (!node.hidden)
        {
            // Set max/min XY for whole tree
            if (node.pos.x + node.width > maxX)
                maxX = node.pos.x + node.width;

            if (node.pos.x < minX)
                minX = node.pos.x;

            if (node.pos.y + node.height > maxY)
                maxY = node.pos.y + node.height;

            if (node.pos.y < minY)
                minY = node.pos.y;
        }
    }

    // Set tree width and height
    tWid = Math.ceil(maxX - minX);
    tHgt = Math.ceil(maxY - minY);

    // Return width and height as a Point(x,y)
    return new Point(tWid, tHgt);
}

// ===============================================================
// Sets node.hidden for all nodes in sub-tree below passed root
// Returns the number of nodes in the sub-tree below passed root
// (TreeNode root, boolean hide)
// ---------------------------------------------------------------
function markSubTreeAsHiddenOrVisible(root, hide)
{
    // Initialize tree size global variable
    gSubTreeSize = 0;

    // Run recursive procedure that increments global var
    walkSubTree(root, hide);

    // Recursion complete - So return tree size
    return gSubTreeSize;
}

// ============================================================
// RECURSIVE routine to visit all TreeNode's below passed root
// (TreeNode t, boolean hide)
// ------------------------------------------------------------
function walkSubTree(t, hide)
{
    var c, s;  // TreeNodes

    // --------------------------------------
    // Mark TreeNode as hidden or visible
    t.hidden = hide;

    // Add to count of num TreeNode's in sub-tree
    if (t.hiddenTreeSize > 0)
        gSubTreeSize += t.hiddenTreeSize;
    else
        gSubTreeSize ++;

    // --------------------------------------
    // Move to next TreeNode in sub-tree
    c = t.child;
    if(c !== null)
    {
        // ***********************************
        // *******   RECURSIVE CALL   ********
        // ***********************************
        walkSubTree(c, hide);
        s = c.sibling;

        while(s != null)
        {
            // ***********************************
            // *******   RECURSIVE CALL   ********
            // ***********************************
            walkSubTree(s, hide);
            s = s.sibling;
        }
    }
}